package course;

import java.util.Arrays;
import java.util.Random;





public class SortTest {
    public static void main(String[] args) {
        //ReversePairsChecker.check(Solution::reversePairs, 50000, 200, 50, true);
    }
    
}

class SolutionSortTest{
    /*LCR 170. 交易逆序对的总数
     * 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
     * 
     * 输入：record = [9, 7, 5, 4, 6]
        输出：8
        解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
     */
    public static int reversePairs(int[] record) {
        if(record == null || record.length < 2)
            return 0;
        // 逆置数组，转化为求小和问题
        for(int i = 0, j = record.length - 1; i < j; i++, j--)
            QuickSortTest.swap(record, i, j);
        return reversePairs1(record, 0, record.length - 1);
    }
    private static int reversePairs1(int[] record, int L, int R){
        if(L == R)
            return 0;
        int mid = L + ((R - L) >> 1);
        int left = reversePairs1(record, L, mid);
        int right = reversePairs1(record, mid + 1, R);
        return reversePairsCore(record, L, mid, R) + left + right;
    }

    private static int reversePairsCore(int[] arr, int L, int mid, int R){
        int resCount = 0, index = 0;
        int[] tempArr = new int[R - L + 1];
        int left = L, right = mid + 1;
        while(left <= mid && right <= R){
            if(arr[right] > arr[left]){
                resCount += R - right + 1;
            }
            tempArr[index++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while(left <= mid){
            tempArr[index++] = arr[left++];
        }
        while(right <= R){
            tempArr[index++] = arr[right++];
        }
        for(int i = 0; i < tempArr.length; i++){
            arr[L + i] = tempArr[i];
        }
        return resCount;
    }
}


// 逆序对问题对数器
/*
 * ReversePairsChecker.check(Solution::reversePairs);                 // 默认参数
   ReversePairsChecker.check(Solution::reversePairs, true);        // 允许负数
   ReversePairsChecker.check(Solution::reversePairs, 5000, 200, 50, true); // 自定义参数
 */
class ReversePairsChecker{
    @FunctionalInterface
    public interface Counter {
        int apply(int[] arr);
    }

    // 一句跑：默认 10000 次、长度≤100、元素∈[0,100]、不含负数
    public static void check(Counter yourCounter) {
        check(yourCounter, 10_000, 100, 100, false);
    }

    // 可选：允许负数
    public static void check(Counter yourCounter, boolean allowNegative) {
        check(yourCounter, 10_000, 100, 100, allowNegative);
    }

    // 全量参数版
    public static void check(Counter yourCounter, int testTime, int maxSize, int maxValue, boolean allowNegative) {
        Random rand = new Random();
        for (int t = 1; t <= testTime; t++) {
            int[] arr = generateRandomArray(rand, maxSize, maxValue, allowNegative);
            int[] a1 = Arrays.copyOf(arr, arr.length);
            int[] a2 = Arrays.copyOf(arr, arr.length);

            int your = yourCounter.apply(a1);        // 你的实现
            int ref  = referenceCounter(a2);         // 官方参考

            if (your != ref) {
                System.out.println("❌ 出错了！第 " + t + " 轮");
                System.out.println("原始数组: " + Arrays.toString(arr));
                System.out.println("你的答案: " + your);
                System.out.println("参考答案: " + ref);
                // 进一步检查：你的方法是否修改了入参（若修改可能是潜在问题）
                int[] probe = Arrays.copyOf(arr, arr.length);
                yourCounter.apply(probe);
                if (!Arrays.equals(probe, arr)) {
                    System.out.println("⚠️ 提示：你的方法修改了入参数组。若题目要求不修改，请自查实现。");
                }
                return;
            }
        }
        System.out.println("✅ 所有测试通过！");
    }

    // —— 参考答案（等价于你贴的力扣官方题解）——
    private static int referenceCounter(int[] record) {
        int len = record.length;
        if (len < 2) return 0;
        int[] copy = Arrays.copyOf(record, len);
        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    private static int reversePairs(int[] record, int left, int right, int[] temp) {
        if (left == right) return 0;
        int mid = left + ((right - left) >>> 1);
        int leftPairs  = reversePairs(record, left, mid, temp);
        int rightPairs = reversePairs(record, mid + 1, right, temp);
        if (record[mid] <= record[mid + 1]) return leftPairs + rightPairs;
        int cross = mergeAndCount(record, left, mid, right, temp);
        return leftPairs + rightPairs + cross;
    }

    private static int mergeAndCount(int[] record, int left, int mid, int right, int[] temp) {
        System.arraycopy(record, left, temp, left, right - left + 1);
        int i = left, j = mid + 1, count = 0;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                record[k] = temp[j++];
            } else if (j == right + 1) {
                record[k] = temp[i++];
            } else if (temp[i] <= temp[j]) {
                record[k] = temp[i++];
            } else {
                record[k] = temp[j++];
                count += (mid - i + 1);
            }
        }
        return count;
    }
    // —— 参考答案结束 —— //

    private static int[] generateRandomArray(Random rand, int maxSize, int maxValue, boolean allowNegative) {
        int size = rand.nextInt(maxSize + 1); // [0, maxSize]
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            int v = rand.nextInt(maxValue + 1); // [0, maxValue]
            if (allowNegative && rand.nextBoolean()) v = -v;
            arr[i] = v;
        }
        return arr;
    }
}
